Search Results

Documents authored by Gudmundsson, Joachim

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.34
Computing a Subtrajectory Cluster from c-Packed Trajectories

Authors: Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We present a near-linear time approximation algorithm for the subtrajectory cluster problem of c-packed trajectories. Given a trajectory T of complexity n, an approximation factor ε, and a desired distance d, the problem involves finding m subtrajectories of T such that their pair-wise Fréchet distance is at most (1 + ε)d. At least one subtrajectory must be of length l or longer. A trajectory T is c-packed if the intersection of T and any ball B with radius r is at most c⋅r in length. Previous results by Gudmundsson and Wong [Gudmundsson and Wong, 2022] established an Ω(n³) lower bound unless the Strong Exponential Time Hypothesis fails, and they presented an O(n³ log² n) time algorithm. We circumvent this conditional lower bound by studying subtrajectory cluster on c-packed trajectories, resulting in an algorithm with an O((c² n/ε²)log(c/ε)log(n/ε)) time complexity.
Cite as

Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Computing a Subtrajectory Cluster from c-Packed Trajectories. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.34,
  author =	{Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Computing a Subtrajectory Cluster from c-Packed Trajectories}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.34},
  URN =		{urn:nbn:de:0030-drops-193364},
  doi =		{10.4230/LIPIcs.ISAAC.2023.34},
  annote =	{Keywords: Subtrajectory cluster, c-packed trajectories, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.35
Shortest Beer Path Queries in Digraphs with Bounded Treewidth

Authors: Joachim Gudmundsson and Yuan Sha

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
A beer digraph G is a real-valued weighted directed graph where some of the vertices have beer stores. A beer path from a vertex u to a vertex v in G is a path in G from u to v that visits at least one beer store. In this paper we consider the online shortest beer path query in beer digraphs with bounded treewidth t. Assume that a tree decomposition of treewidth t on a beer digraph with n vertices is given. We show that after O(t³n) time preprocessing on the beer digraph, (i) a beer distance query can be answered in O(t³α(n)) time, where α(n) is the inverse Ackermann function, and (ii) a shortest beer path can be reported in O(t³α(n)L) time, where L is the number of edges on the path. In the process we show an improved O(t³α(n)L) time shortest path query algorithm, compared with the currently best O(t⁴α(n)L) time algorithm [Chaudhuri & Zaroliagis, 2000]. We also consider queries in a dynamic setting where the weight of an edge in G can change over time. We show two data structures. Assume t is constant and let β be any constant in (0,1). The first data structure uses O(n) preprocessing time, answers a beer distance query in O(α(n)) time and reports a shortest beer path in O(α(n) L) time. It can be updated in O(n^β) time after an edge weight change. The second data structure has O(n) preprocessing time, answers a beer distance query in O(log n) time, reports a shortest beer path in O(log n + L) time, and can be updated in O(log n) time after an edge weight change.
Cite as

Joachim Gudmundsson and Yuan Sha. Shortest Beer Path Queries in Digraphs with Bounded Treewidth. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2023.35,
  author =	{Gudmundsson, Joachim and Sha, Yuan},
  title =	{{Shortest Beer Path Queries in Digraphs with Bounded Treewidth}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.35},
  URN =		{urn:nbn:de:0030-drops-193379},
  doi =		{10.4230/LIPIcs.ISAAC.2023.35},
  annote =	{Keywords: Graph algorithms, Shortest Path, Data structures, Bounded treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.26
Oriented Spanners

Authors: Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented 𝒪(1)-spanner.
Cite as

Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong. Oriented Spanners. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2023.26,
  author =	{Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Oriented Spanners}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.26},
  URN =		{urn:nbn:de:0030-drops-186796},
  doi =		{10.4230/LIPIcs.ESA.2023.26},
  annote =	{Keywords: computational geometry, spanner, oriented graph, greedy triangulation}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2023
LIPIcs, Volume 258, SoCG 2023, Complete Volume

Authors: Erin W. Chambers and Joachim Gudmundsson

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
LIPIcs, Volume 258, SoCG 2023, Complete Volume
Cite as

39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1-1058, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{chambers_et_al:LIPIcs.SoCG.2023,
  title =	{{LIPIcs, Volume 258, SoCG 2023, Complete Volume}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{1--1058},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023},
  URN =		{urn:nbn:de:0030-drops-178498},
  doi =		{10.4230/LIPIcs.SoCG.2023},
  annote =	{Keywords: LIPIcs, Volume 258, SoCG 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Erin W. Chambers and Joachim Gudmundsson

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2023.0,
  author =	{Chambers, Erin W. and Gudmundsson, Joachim},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.0},
  URN =		{urn:nbn:de:0030-drops-178501},
  doi =		{10.4230/LIPIcs.SoCG.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.45
Augmenting Graphs to Minimize the Radius

Authors: Joachim Gudmundsson, Yuan Sha, and Fan Yao

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3-ε)-approximation algorithm, for any ε > 0, unless P = NP. We also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth.
Cite as

Joachim Gudmundsson, Yuan Sha, and Fan Yao. Augmenting Graphs to Minimize the Radius. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2021.45,
  author =	{Gudmundsson, Joachim and Sha, Yuan and Yao, Fan},
  title =	{{Augmenting Graphs to Minimize the Radius}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{45:1--45:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.45},
  URN =		{urn:nbn:de:0030-drops-154785},
  doi =		{10.4230/LIPIcs.ISAAC.2021.45},
  annote =	{Keywords: graph augmentation, radius, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.9
Approximating the Packedness of Polygonal Curves

Authors: Joachim Gudmundsson, Yuan Sha, and Sampson Wong

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In 2012 Driemel et al. [Anne Driemel et al., 2012] introduced the concept of c-packed curves as a realistic input model. In the case when c is a constant they gave a near linear time (1+ε)-approximation algorithm for computing the Fréchet distance between two c-packed polygonal curves. Since then a number of papers have used the model. In this paper we consider the problem of computing the smallest c for which a given polygonal curve in ℝ^d is c-packed. We present two approximation algorithms. The first algorithm is a 2-approximation algorithm and runs in O(dn² log n) time. In the case d = 2 we develop a faster algorithm that returns a (6+ε)-approximation and runs in O((n/ε³)^{4/3} polylog (n/ε))) time. We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of c-packedness is a useful realistic input model for many curves and trajectories.
Cite as

Joachim Gudmundsson, Yuan Sha, and Sampson Wong. Approximating the Packedness of Polygonal Curves. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2020.9,
  author =	{Gudmundsson, Joachim and Sha, Yuan and Wong, Sampson},
  title =	{{Approximating the Packedness of Polygonal Curves}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.9},
  URN =		{urn:nbn:de:0030-drops-133530},
  doi =		{10.4230/LIPIcs.ISAAC.2020.9},
  annote =	{Keywords: Computational geometry, trajectories, realistic input models}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.7
On β-Plurality Points in Spatial Voting Games

Authors: Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).
Cite as

Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton. On β-Plurality Points in Spatial Voting Games. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.7,
  author =	{Aronov, Boris and de Berg, Mark and Gudmundsson, Joachim and Horton, Michael},
  title =	{{On \beta-Plurality Points in Spatial Voting Games}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.7},
  URN =		{urn:nbn:de:0030-drops-121651},
  doi =		{10.4230/LIPIcs.SoCG.2020.7},
  annote =	{Keywords: Computational geometry, Spatial voting theory, Plurality point, Computational social choice}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.30
Local Routing in Sparse and Lightweight Geometric Graphs

Authors: Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos, Bengt J. Nilsson, and André van Renssen

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Bose and Morin, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.
Cite as

Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos, Bengt J. Nilsson, and André van Renssen. Local Routing in Sparse and Lightweight Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.ISAAC.2019.30,
  author =	{Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, Andr\'{e}},
  title =	{{Local Routing in Sparse and Lightweight Geometric Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.30},
  URN =		{urn:nbn:de:0030-drops-115269},
  doi =		{10.4230/LIPIcs.ISAAC.2019.30},
  annote =	{Keywords: Computational geometry, Spanners, Routing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.9
Shortcuts for the Circle

Authors: Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.
Cite as

Sang Won Bae, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, and Christos Levcopoulos. Shortcuts for the Circle. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.ISAAC.2017.9,
  author =	{Bae, Sang Won and de Berg, Mark and Cheong, Otfried and Gudmundsson, Joachim and Levcopoulos, Christos},
  title =	{{Shortcuts for the Circle}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.9},
  URN =		{urn:nbn:de:0030-drops-82133},
  doi =		{10.4230/LIPIcs.ISAAC.2017.9},
  annote =	{Keywords: Computational geometry, graph augmentation problem, circle, shortcut, diameter}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.37
Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements

Authors: Serge Gaspers, Joachim Gudmundsson, Julián Mestre, and Stefan Rümmele

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Given a line segment I=[0,L], the so-called barrier, and a set of n sensors with varying ranges positioned on the line containing I, the barrier coverage problem is to move the sensors so that they cover I, while minimising the total movement. In the case when all the sensors have the same radius the problem can be solved in O(n log n) time (Andrews and Wang, Algorithmica 2017). If the sensors have different radii the problem is known to be NP-hard to approximate within a constant factor (Czyzowicz et al., ADHOC-NOW 2009). We strengthen this result and prove that no polynomial time \rho^{1-\epsilon}-approximation algorithm exists unless P=NP, where \rho is the ratio between the largest radius and the smallest radius. Even when we restrict the number of sensors that are allowed to move by a parameter k, the problem turns out to be W[1]-hard. On the positive side we show that a ((2+\epsilon)\rho+2/\epsilon)-approximation can be computed in O(n^3/\epsilon^2) time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.
Cite as

Serge Gaspers, Joachim Gudmundsson, Julián Mestre, and Stefan Rümmele. Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2017.37,
  author =	{Gaspers, Serge and Gudmundsson, Joachim and Mestre, Juli\'{a}n and R\"{u}mmele, Stefan},
  title =	{{Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.37},
  URN =		{urn:nbn:de:0030-drops-82591},
  doi =		{10.4230/LIPIcs.ISAAC.2017.37},
  annote =	{Keywords: Barrier coverage, Sensor movement, Approximation, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.42
Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons

Authors: Joachim Gudmundsson and Rasmus Pagh

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. min-wise hashing) to these point sets would require time proportional to the number of points. We seek to achieve time that is much lower than direct approaches. Technically, we introduce new primitives for range-efficient consistent sampling (of independent interest), and show how to turn such samples into LSH values. Another application of our technique is a data structure for quickly estimating the size of the intersection or union of a set of preprocessed polygons. Curiously, our consistent sampling method uses transformation to a geometric problem.
Cite as

Joachim Gudmundsson and Rasmus Pagh. Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2017.42,
  author =	{Gudmundsson, Joachim and Pagh, Rasmus},
  title =	{{Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.42},
  URN =		{urn:nbn:de:0030-drops-82316},
  doi =		{10.4230/LIPIcs.ISAAC.2017.42},
  annote =	{Keywords: Locality-sensitive hashing, probability distribution, polygon, min-wise hashing, consistent sampling}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.13
Turbocharging Treewidth Heuristics

Authors: Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution.
Cite as

Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging Treewidth Heuristics. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.IPEC.2016.13,
  author =	{Gaspers, Serge and Gudmundsson, Joachim and Jones, Mitchell and Mestre, Juli\'{a}n and R\"{u}mmele, Stefan},
  title =	{{Turbocharging Treewidth Heuristics}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.13},
  URN =		{urn:nbn:de:0030-drops-69322},
  doi =		{10.4230/LIPIcs.IPEC.2016.13},
  annote =	{Keywords: tree decomposition, heuristic, fixed-parameter tractability, local search}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.32
Faster Algorithms for Computing Plurality Points

Authors: Mark de Berg, Joachim Gudmundsson, and Mehran Mehr

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector <w_1(v), ...,w_d(v)> and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).
Cite as

Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster Algorithms for Computing Plurality Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2016.32,
  author =	{de Berg, Mark and Gudmundsson, Joachim and Mehr, Mehran},
  title =	{{Faster Algorithms for Computing Plurality Points}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.32},
  URN =		{urn:nbn:de:0030-drops-59248},
  doi =		{10.4230/LIPIcs.SoCG.2016.32},
  annote =	{Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points}
}
Document
DOI: 10.4230/DagRep.2.12.89
Representation, Analysis and Visualization of Moving Objects (Dagstuhl Seminar 12512)

Authors: Joachim Gudmundsson, Patrick Laube, and Emiel Van Loon

Published in: Dagstuhl Reports, Volume 2, Issue 12 (2013)

Abstract
From December 16 to December 21, 2012, the Dagstuhl Seminar 12512 "Representation, Analysis and Visualization of Moving Objects" was held in Schloss Dagstuhl -- Leibniz Center for Informatics. The major goal of this seminar was to bring together the diverse and fast growing, research community that is involved in developing better computational techniques for spatio-temporal object representation, data mining, and visualization of moving object data. The participants included experts from fields such as computational geometry, data mining, visual analytics, GIS science, urban planning and movement ecology. Most of the participants came from academic institutions but some also from government agencies and industry. The seminar has led to a fruitful exchange of ideas between different disciplines, to the creation of new interdisciplinary collaborations and to recommendations for future research directions. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper.
Cite as

Joachim Gudmundsson, Patrick Laube, and Emiel Van Loon. Representation, Analysis and Visualization of Moving Objects (Dagstuhl Seminar 12512). In Dagstuhl Reports, Volume 2, Issue 12, pp. 89-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{gudmundsson_et_al:DagRep.2.12.89,
  author =	{Gudmundsson, Joachim and Laube, Patrick and Van Loon, Emiel},
  title =	{{Representation, Analysis and Visualization of Moving Objects (Dagstuhl Seminar 12512)}},
  pages =	{89--106},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{12},
  editor =	{Gudmundsson, Joachim and Laube, Patrick and Van Loon, Emiel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.12.89},
  URN =		{urn:nbn:de:0030-drops-39966},
  doi =		{10.4230/DagRep.2.12.89},
  annote =	{Keywords: movement analysis, algorithms, visualization, geo-ecology, urban planning}
}
Document
DOI: 10.4230/DagSemProc.10491.5
10491 Results of the break-out group: Gulls Data

Authors: Emiel van Loon, Jörg-Rüdiger Sack, Kevin Buchin, Maike Buchin, Mark de Berg, Marc van Kreveld, Joachim Gudmundsson, and David Mountain

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
A classification of gull behaviour was produced by the group, led by domain expert Emiel van Loon, who provided additional context including that gull trips are typically composed of distinct segments, that gull trips are rarely single purpose, and that there is very little diurnal pattern to activities. The classification produced is not intended to be complete, or non overlapping. Furthermore, the group considered how the attributes in the gulls dataset could be used in algorithms to automatically classify the dataset into distinct spatial patterns, and associate this with gull behaviours.
Cite as

Emiel van Loon, Jörg-Rüdiger Sack, Kevin Buchin, Maike Buchin, Mark de Berg, Marc van Kreveld, Joachim Gudmundsson, and David Mountain. 10491 Results of the break-out group: Gulls Data. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{vanloon_et_al:DagSemProc.10491.5,
  author =	{van Loon, Emiel and Sack, J\"{o}rg-R\"{u}diger and Buchin, Kevin and Buchin, Maike and de Berg, Mark and van Kreveld, Marc and Gudmundsson, Joachim and Mountain, David},
  title =	{{10491 Results of the break-out group: Gulls Data}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.5},
  URN =		{urn:nbn:de:0030-drops-29912},
  doi =		{10.4230/DagSemProc.10491.5},
  annote =	{Keywords: Movement classification, Trajectory segmentation}
}
Document
DOI: 10.4230/DagSemProc.10491.7
10491 Results of the break-out group: Similarity measures

Authors: Joachim Gudmundsson, Harvey Miller, Rodrigo Silveira, Mathias Versichele, and Stefan van der Spek

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
In the group discussions we discussed distance measures focussing on real world applications specifically on domain areas where trajectories have been generated by animals (birds, primates...) and humans in urban areas.
Cite as

Joachim Gudmundsson, Harvey Miller, Rodrigo Silveira, Mathias Versichele, and Stefan van der Spek. 10491 Results of the break-out group: Similarity measures. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.10491.7,
  author =	{Gudmundsson, Joachim and Miller, Harvey and Silveira, Rodrigo and Versichele, Mathias and van der Spek, Stefan},
  title =	{{10491 Results of the break-out group: Similarity measures}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.7},
  URN =		{urn:nbn:de:0030-drops-29893},
  doi =		{10.4230/DagSemProc.10491.7},
  annote =	{Keywords: Similarity, Movement Analysis}
}
Document
DOI: 10.4230/DagSemProc.09451.1
09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining

Authors: Gautam Das, Joachim Gudmundsson, Rolf Klein, Christian Knauer, and Michiel Smid

Published in: Dagstuhl Seminar Proceedings, Volume 9451, Geometric Networks, Metric Space Embeddings and Spatial Data Mining (2010)

Abstract
From November 1 to 6, 2009, the Dagstuhl Seminar 09451 ``Geometric Networks, Metric Space Embeddings and Spatial Data Mining'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Gautam Das, Joachim Gudmundsson, Rolf Klein, Christian Knauer, and Michiel Smid. 09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining. In Geometric Networks, Metric Space Embeddings and Spatial Data Mining. Dagstuhl Seminar Proceedings, Volume 9451, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:DagSemProc.09451.1,
  author =	{Das, Gautam and Gudmundsson, Joachim and Klein, Rolf and Knauer, Christian and Smid, Michiel},
  title =	{{09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining}},
  booktitle =	{Geometric Networks, Metric Space Embeddings and Spatial Data Mining},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9451},
  editor =	{Gautam Das and Joachim Gudmundsson and Rolf Klein and Christian Knauer and Michiel Smid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09451.1},
  URN =		{urn:nbn:de:0030-drops-24380},
  doi =		{10.4230/DagSemProc.09451.1},
  annote =	{Keywords: Geometric networks, metric space embeddings, spatial data mining, spanners, dilation, distortion}
}
Document
DOI: 10.4230/DagSemProc.06481.1
06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings

Authors: Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff

Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

Abstract
The Dagstuhl Seminar 06481 ``Geometric Networks and Metric Space Embeddings'' was held from November~26 to December~1, 2006 in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. In this paper we describe the seminar topics, we have compiled a list of open questions that were posed during the seminar, there is a list of all talks and there are abstracts of the presentations given during the seminar. Links to extended abstracts or full papers are provided where available.
Cite as

Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff. 06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.06481.1,
  author =	{Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander},
  title =	{{06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.1},
  URN =		{urn:nbn:de:0030-drops-10291},
  doi =		{10.4230/DagSemProc.06481.1},
  annote =	{Keywords: Geometric networks, metric space embeddings, phylogenetic networks, spanners, dilation, distortion}
}
Document
DOI: 10.4230/DagSemProc.04301.2
A Simple Algorithm for I/O-efficiently Pruning Dense Spanners

Authors: Joachim Gudmundsson and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
Given a geometric graph $G=(S,E)$ in $R^d$ with constant dilation $t$, and a positive constant $\epsilon$, we show how to construct a $(1+\epsilon)$-spanner of $G$ with $O(|S|)$ edges using $O(sort(|E|))$ I/O operations.
Cite as

Joachim Gudmundsson and Jan Vahrenhold. A Simple Algorithm for I/O-efficiently Pruning Dense Spanners. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.04301.2,
  author =	{Gudmundsson, Joachim and Vahrenhold, Jan},
  title =	{{A Simple Algorithm for I/O-efficiently Pruning Dense Spanners}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.2},
  URN =		{urn:nbn:de:0030-drops-1566},
  doi =		{10.4230/DagSemProc.04301.2},
  annote =	{Keywords: No keywords}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact